/**
 * 题目：2025/09/14 考试 T3 最惡の記者 6
 * 完成时间：2025/09/14 15:30
 */
#include <bits/stdc++.h>
#define range(i, b, e) for (auto i(b); i != (e); i++)
#define rep(i, b, e) for (auto i(b); i <= (e); i++)
#define req(i, b, e) for (auto i(b); i >= (e); i--)
using namespace std;
typedef long long LL;
typedef pair<int, int> Pii;

const int N = 1e5;
int n, k;
int a[N+5];
int lst[N+5][5];
LL ans;

#define lc u<<1
#define rc u<<1 | 1
#define lson lc, l, mid
#define rson rc, mid+1, r
#define vertex int u = 1, int l = 1, int r = n

int sum[N*4 + 5][4], cnt[N*4 + 5][16];

void Pushup(vertex) {
	int state = 0;
	rep(w, 0, 3) {
		if (sum[u][w]) state |= 1<<w;
	}
	rep(i, 0, 15) cnt[u][i] = 0;
	if (l < r) req(i, 15, 0) cnt[u][i|state] += cnt[lc][i] + cnt[rc][i];
	else cnt[u][state] = 1;
}

void Build(vertex) {
	if (l != r) {
		int mid = (l+r) >> 1;
		Build(lson);
		Build(rson);
	}
	Pushup(u, l, r);
}

void Update(int ql, int qr, int w, int v, vertex) {
	if (ql <= l && r <= qr) sum[u][w] += v;
	else {
		int mid = (l+r) >> 1;
		if (ql <= mid) Update(ql, qr, w, v, lson);
		if (qr > mid) Update(ql, qr, w, v, rson);
	}
	Pushup(u, l, r);
}

#undef lc
#undef rc
#undef lson
#undef rson
#undef vertex

void upd(int x, int v) {
	rep(i, 0, 3) {
		if (lst[x][i+1] < lst[x][i]) Update(lst[x][i+1] + 1, lst[x][i], i, v);
	}
}

int main() {
	freopen("reporter.in", "r", stdin);
	freopen("reporter.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	cin >> n >> k;
	Build();
	for (int i = 1, x; i <= n; i++) {
		cin >> x;
		upd(x, -1);
		req(j, 3, 0) lst[x][j+1] = lst[x][j];
		lst[x][0] = i;
		upd(x, 1);
		rep(j, 0, 15) {
			if ((j | ((1<<k) - 1)) == j) ans += cnt[1][j];
		}
	}
	cout << ans;
	return 0;
}
